Voice-mail service systems are well known in the art. They principally provide to a calling party the ability to send a voice message to a called party without contacting another human being e.g., answering service operator, in the process, and enable the called party to retrieve those messages at will via his or her telephone, also without intervention of another human being. These systems also typically formulate a header for each message that identifies, e.g., when the message was received and the telephone number and/or identity of the calling party. The called party can retrieve and review the header information--for example, to determine what new messages have been received--without retrieving and listening to the messages themselves. An example of such a system, is the AT&T Audix.RTM. voice-mail service system.